class Solution:
    def kthSmallest(self, matrix: list, k: int) -> int:
        """这题的描述超级有问题,可以有重复的"""
        res_set = set()
        max_num = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if len(res_set) < k:
                    res_set.add(matrix[i][j])
                    max_num = max(max_num, matrix[i][j])
                else:
                    if matrix[i][j] < max_num and matrix[i][j] not in res_set:
                        res_set.remove(max_num)
                        res_set.add(matrix[i][j])
                        max_num = max(res_set)
        return max_num


class Solution:
    def kthSmallest(self, matrix: list, k: int) -> int:
        mid_list = []
        for lists in matrix:
            mid_list += lists
        mid_list.sort()
        return mid_list[k-1]


a = Solution()
print(a.kthSmallest(matrix=[[1, 5, 9], [10, 11, 13], [12, 13, 15]], k=8))
